package com.lw.leetcode.stack.b;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * 1129. 颜色交替的最短路径
 *
 * @author liw
 * @version 1.0
 * @date 2022/4/5 15:51
 */
public class ShortestAlternatingPaths {

    public static void main(String[] args) {
        ShortestAlternatingPaths test = new ShortestAlternatingPaths();

        // {0,1,-1}
//        int[][] as = {{0, 1}, {1, 2}};
//        int[][] bs = {};
//        int k = 3;

        // {0,1,-1}
//        int[][] as = {{0,1}};
//        int[][] bs = {{2,1}};
//        int k = 3;

        // {0,-1,-1}
//        int[][] as = {{1,0}};
//        int[][] bs = {{2,1}};
//        int k = 3;

        // {0,1,2}
        int[][] as = {{0, 1}};
        int[][] bs = {{1, 2}};
        int k = 3;

        // {0,1,1}
//        int[][] as = {{0, 1}, {0, 2}};
//        int[][] bs = {{1, 0}};
//        int k = 3;

        int[] ints = test.shortestAlternatingPaths(k, as, bs);

        System.out.println(Arrays.toString(ints));
    }


    public int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
        Map<Integer, List<Integer>> rmap = new HashMap<>();
        for (int[] redEdge : redEdges) {
            rmap.computeIfAbsent(redEdge[0], v -> new ArrayList<>()).add(redEdge[1]);
        }
        Map<Integer, List<Integer>> bmap = new HashMap<>();
        for (int[] blueEdge : blueEdges) {
            bmap.computeIfAbsent(blueEdge[0], v -> new ArrayList<>()).add(blueEdge[1]);
        }
        int[] rarr = new int[n];
        int[] barr = new int[n];
        Arrays.fill(rarr, Integer.MAX_VALUE - 1);
        Arrays.fill(barr, Integer.MAX_VALUE - 1);
        rarr[0] = 0;
        barr[0] = 0;
        Stack<Integer> aset = new Stack<>();
        Stack<Integer> bset = new Stack<>();
        Stack<Integer> ac = new Stack<>();
        Stack<Integer> bc = new Stack<>();
        aset.add(0);
        bset.add(0);
        while (!aset.isEmpty() || !bset.isEmpty()) {
            while (!aset.isEmpty()) {
                int index = aset.pop();
                int v = barr[index];
                List<Integer> list = rmap.get(index);
                if (list != null) {
                    for (int i : list) {
                        if (v + 1 < rarr[i]) {
                            rarr[i] = v + 1;
                            ac.add(i);
                        }
                    }
                }
            }
            while (!bset.isEmpty()) {
                int index = bset.pop();
                int v = rarr[index];
                List<Integer> list = bmap.get(index);
                if (list != null) {
                    for (int i : list) {
                        if (v + 1 < barr[i]) {
                            barr[i] = v + 1;
                            bc.add(i);
                        }
                    }
                }
            }
            bset.addAll(ac);
            aset.addAll(bc);
            ac.clear();
            bc.clear();
        }
        for (int i = 0; i < n; i++) {
            rarr[i] = Math.min(rarr[i], barr[i]);
            if (rarr[i] == Integer.MAX_VALUE - 1) {
                rarr[i] = -1;
            }
        }
        return rarr;
    }

}
